Computing systems—i.e. devices capable of processing electronic data such as computers, telephones, Personal Digital Assistants (PDA), etc.—communicate with other computing systems by exchanging data messages according to a communications protocol that is recognizable by the systems. A system utilizes filters to analyze messages that are sent and/or received by the system and to determine if and how the messages will be processed further.
Filters are used to process a diverse assortment of documents and messages. Data processed by filters is frequently arranged in a hierarchical manner, generally as a result of an addressing or naming system that is used to uniquely identify or locate the data. For example, Internet resources are named according to Universal Resource Identifiers (URI) that reflect a hierarchical structure. The URI “http://www.mycorp.com/products” identifies a web page called “products” that is hosted on “www.mycorp.com” and is organized according to a particular URI scheme (“http”). In this particular example, “http” is a root of the hierarchy, “www.mycorp.com” is a subordinate of the root, and “/products” is a subordinate of “www.mycorp.com”.
In addition to Internet resources, a distributed system frequently utilizes hierarchical namespaces as a natural way to organize and express the topology of system resources such as servers, printers, etc. For example, the following hierarchical name scheme is a natural and convenient way of organizing MyCorp's web servers:                http://www.mycorp.com/machines/wa/seattle/server1.        
In this particular example, the namespace utilizes the hierarchical structure to identify particular resources (“machines”) in particular geographical areas (“wa” and “seattle”), which is a common scheme.
Whenever data is organized hierarchically, decision logic used to process the data also develops a hierarchical flavor. Thus, in the previous example, a corporation (“MyCorp”) may develop a set of data processing rules that apply to machines regardless of the city and state in which the machines are located by orienting the rules about the name prefix “http://www.mycorp.com/machines”. Another set of data processing rules that apply specifically to machines located in Washington would utilize the name prefix http://www.mycorp.com/machines/wa”.
A common application that uses processing rules based on name prefixes is message routing. Message routers store route tables that are comprised of filters and destinations, a destination being associated with each filter. To route a message, a router matches the message against its internal filter table to produce a set of matching filters. The router then forwards the message to the destinations associated with each matching filter.
Such a router is relatively inefficient because the message router must try every input against each filter stored in the route table. Since route tables typically contain thousands of entries, the process of comparing an input with each and every filter can consume significant time and resources. If the number of comparisons is reduced, then the process would become more efficient.
Another problem is that, since multiple routes (i.e. filters) in a route table have overlapping scope, it is not uncommon for an input to match multiple filters. All matching filters that match a given input are returned in no particular order. If an order can be established and the results returned according to that order, then processing could be streamlined even further.